Shortest distance from all buildings

Time: O(KxMxN); Space: O(MxN); hard

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right.

You are given a 2D grid of values 0, 1 or 2, where: * Each 0 marks an empty land which you can pass by freely. * Each 1 marks a building which you cannot pass through. * Each 2 marks an obstacle which you cannot pass through. Have you met this question in a real interview?

Example 1:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output: 7

Explanation:

  • In this example, there are three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).

  • 1 - 0 - 2 - 0 - 1

  • |   |   |   |   |

  • 0 - 0 - 0 - 0 - 0

  • |   |   |   |   |

  • 0 - 0 - 1 - 0 - 0

  • The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.

  • So return 7.

Example 2:

Input: [[1,0],[0,0]]

Output: 1

In this example, there is one buildings at (0,0).

1 - 0
|   |
0 - 0

The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.

[1]:

class Solution1(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        def bfs(grid, dists, cnts, x, y):
            dist, m, n = 0, len(grid), len(grid[0])
            visited = [[False for _ in range(n)] for _ in range(m)]

            pre_level = [(x, y)]
            visited[x][y] = True
            while pre_level:
                dist += 1
                cur_level = []
                for i, j in pre_level:
                    for dir in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        I, J = i+dir[0], j+dir[1]
                        if 0 <= I < m and 0 <= J < n and grid[I][J] == 0 and not visited[I][J]:
                            cnts[I][J] += 1
                            dists[I][J] += dist
                            cur_level.append((I, J))
                            visited[I][J] = True

                pre_level = cur_level


        m, n, cnt = len(grid),  len(grid[0]), 0
        dists = [[0 for _ in range(n)] for _ in range(m)]
        cnts = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    cnt += 1
                    bfs(grid, dists, cnts, i, j)

        shortest = float("inf")
        for i in range(m):
            for j in range(n):
                if dists[i][j] < shortest and cnts[i][j] == cnt:
                    shortest = dists[i][j]

        return shortest if shortest != float("inf") else -1

[2]:

s = Solution1()
grid = [
    [1,0,2,0,1],
    [0,0,0,0,0],
    [0,0,1,0,0]
]
assert s.shortestDistance(grid) == 7